import java.util.Arrays;



public class Leetcode2055 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(platesBetweenCandles("***|**|*****|**||**|*", new int[][]{{1, 17}, {4, 5}})));
        System.out.println(Arrays.toString(platesBetweenCandles("***", new int[][]{{2, 2}})));
    }

    private static final char CANDLE = '|';
    private static final char PLATE = '*';

    public static int[] platesBetweenCandles(String s, int[][] queries) {
        int n = s.length();
        int[] dpLeft = getDpLeft(s);
        int[] dpRight = getDpRight(s);
        int[] prefix = new int[s.length()];
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == CANDLE) {
                prefix[i] = prefix[i - 1];
            } else {
                prefix[i] = prefix[i - 1] + 1;
            }
        }

        int[] res = new int[queries.length];

        for (int i = 0; i < queries.length; i++) {
            if (dpRight[queries[i][0]] == -1 || dpLeft[queries[i][1]] == -1) {
                res[i] = 0;
                continue;
            }

            int start = queries[i][0] + dpRight[queries[i][0]];
            int end = queries[i][1] - dpLeft[queries[i][1]];
            if (start >= queries[i][1] || end <= queries[i][0] || start == end) {
                res[i] = 0;
                continue;
            }

            res[i] = prefix[end] - prefix[start];
        }

        return res;
    }

    private static int[] getDpLeft(String s) {
        int[] dpLeft = new int[s.length()];
        int n = s.length();

        int left = -1;
        boolean first = true;
        for (int i = 0; i < n; i++) {
            dpLeft[i] = left;
            if (s.charAt(i) == CANDLE) {
                left = 1;
                first = false;
                dpLeft[i] = 0;
            } else if (!first && s.charAt(i) == PLATE) {
                ++left;
            }
        }

        return dpLeft;
    }

    private static int[] getDpRight(String s) {
        int[] dpRight = new int[s.length()];

        int n = s.length();
        int right = -1;
        boolean first = true;
        for (int i = n - 1; i >= 0; i--) {
            dpRight[i] = right;
            if (s.charAt(i) == CANDLE) {
                right = 1;
                first = false;
                dpRight[i] = 0;
            } else if (!first && s.charAt(i) == PLATE) {
                ++right;
            }
        }

        return dpRight;
    }
}
